[투포인터] 백준 1940번

1. 문제
2. 문제 분석
3. 슈도코드 작성
4. 코드 작성

참고)
 CPU 연산은 1초에 1억번 (시간복잡도 계산하며 풀기)

문제

주몽의 명령 갑옷만들기

• 갑옷을 만드는데 필요한 재료 2가지
• 재료의 합 M ( 1 <= M <= 10,000,000 )
• 재료의 개수 N ( 1 <= N <= 15,000)

문제 분석

• 투포인터 사용 (start point , end point)

투포인터 이동 원칙

• A[i] + A[j] > M : j—;    번호의 합이 M보다 크면 끝 번호 인덱스(j)를 한칸 아래로 이동
• A[i] + A[j] < M : i++;    번호의 합이 M보다 작으면 시작 번호 인덱스(i)를 한칸 위로 이동
• A[i] + A[j] == M : i++, j—;    양쪽 포인터를 모두 이동시키고 count를 증가

• 두가지 포인터를 이용하여, 값을 계산하며 추정
  • 정렬 필요 : 투포인터를 사용하기 위해서는 정렬을 해야함 (2초내 연산이므로 사용해도 괜찮다)

중요)  정렬의 시간복잡도 : O(NlogN)
ex) 재료의 개수 : 15,000
      15000 * (3 + log15)

슈도코드 작성

N(재료의 개수) , M(갑옷이 되는 번호) 저장하기
for (N만큼 반복)
{
   재료 배열 저장하기
}
 
재료 배열 정렬하기
 
while( i <j )
{
    if (재료 합 < M)  시작 포인터 위치를 한칸 위로 이동
    else if (재료 합 > M) 끝 포인터 위치를 한칸 아래로 이동
    else 카운트값 증가, 양쪽 포인터 각각 이동
}
count 출력하기

코드 작성

• 입력값 (bufferedReader)
• 공백 파싱 (StringTokenizer)
• 타입 변환 (parse[타입])
• 배열 정렬(java.util.Arrays)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
 
public class App {
    public static void main(String[] args) throws Exception {
        
 
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(buf.readLine());
        int M = Integer.parseInt(buf.readLine());
        int[] array = new int[N];
        
        StringTokenizer st = new StringTokenizer(buf.readLine());
 
        for (int i = 0; i < N; i++){
            array[i] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(array);
        
        int count = 0;
        int i = 0;
        int j = N-1;
        while( i < j){
            if (array[i] + array[j] < M){
                i++;
            }
            else if (array[i] + array[j] > M){
                j--;
            }
            else{
                count++;
                i++;
                j--;
            }
        }
 
        System.out.printf("count = %d", count);
        buf.close();
 
    }
}

---

🔗 관련

• (투포인터) 백준 1253 — 정렬 + 투포인터로 두 원소 합 찾기 동일 패턴